package com.sx.sx1.lintcode.day717;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC1190 {

    static class Solution {
        /**
         * @param s: a string
         * @param d: List[str]
         * @return: return a string
         */
        public String findLongestWord(String s, List<String> d) {
            // LC 1190 · 通过删除字母匹配到字典里最长单词  LK 524. 通过删除字母匹配到字典里最长单词  中等
            //同力扣524，力扣的题目更容易读懂
            String ans = "";
            for (String s1 : d) {
                boolean b= issubstr(s,s1);
                //System.out.println(s1+" b="+ b +" compareto:"+ (ans.compareTo(s1) >0));
                if(b){
                    if(ans.equals("")) ans = s1;
                    else if(ans.length() < s1.length()) ans = s1;
                    else if(ans.length() == s1.length() && ans.compareTo(s1) >0) ans=s1;
                }
            }
           return ans;
        }

        //检查s1是否是s的子序列
        public boolean issubstr(String s,String s1){
            if(s.length()<s1.length()) return false;
            int L=0;
            int R =0;

            while (L<s.length() && R< s1.length()){
                if(s.charAt(L) == s1.charAt(R)){
                    R++;
                }
                L++;

                if(R == s1.length()) break;
            }
            return R == s1.length();
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.findLongestWord("abpcplea",new ArrayList<>(Arrays.asList("ale","apple","monkey","plea"))));
        System.out.println(obj.findLongestWord("abpcplea",new ArrayList<>(Arrays.asList("a","b","c","d"))));
        System.out.println(obj.findLongestWord("aaa",new ArrayList<>(Arrays.asList("aaa","aa","a","d"))));

    }
}

/*
"aaa"
["aaa","aa","a"]
输出数据
"a"
期望答案
"aaa"
 */
/*
LeetCode Logo
题库
Plus 会员
0

avatar
524. 通过删除字母匹配到字典里最长单词
中等
335
相关企业
给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。



示例 1：

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"
示例 2：

输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"


提示：

1 <= s.length <= 1000
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 1000
s 和 dictionary[i] 仅由小写英文字母组成
通过次数
99.7K
提交次数
199.1K
通过率
50.0%
请问您在哪类招聘中遇到此题？
1/5
社招
校招
实习
未遇到
相似题目
相关标签
贡献者

© 2023 领扣网络（上海）有限公司

Java

智能模式





12345
class Solution {
    public String findLongestWord(String s, List<String> dictionary) {

    }
}

控制台

运行
提交

示例 1：

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"
示例 2：

输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"

 */

/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有197条未读消息，请及时查看
1190 · 通过删除字母匹配到字典里最长单词
算法
中等
通过率
49%

题目
题解10
笔记
讨论14
排名
记录
描述
给定字符串和字符串字典，找到字典中可以通过删除给定字符串的某些字符所形成的最长字符串。
如果有多个可能的结果，则返回具有最小字典顺序的最长单词。 如果没有可能的结果，则返回空字符串。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


输入中的所有字符串仅包含小写字母。
字典的大小不会超过1,000。
输入中所有字符串的长度不会超过1,000。

样例
案例 1:

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

输出:
"apple"
案例 2:

输入:
s = "abpcplea", d = ["a","b","c"]

输出:
"a"
标签
企业
Google
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
已开启智能提示
发起考试
30 分 00 秒
12345678910

控制台
        历史提交

 */
